package com.leetcode.leetcode2;

import java.util.Arrays;

/**
 * 删除并获得点数
 *
 * @author luhd
 * @date 2023-07-25
 */
public class Practice740 {

    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     *
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
     *
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     * 输入：nums = [3,4,2]
     * 输出：6
     * 解释：
     * 删除 4 获得 4 个点数，因此 3 也被删除。
     * 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
     */
    public static void main(String[] args) {
        int[] nums = {1,1,1};
        System.out.println(deleteAndEarn(nums));
    }

    public static int deleteAndEarn(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int max = Arrays.stream(nums).max().getAsInt();
        int[] all = new int[max+2];
        Arrays.fill(all,0);
        for (int num : nums) {
            all[num]++;
        }
        int[] dp = new int[max+2];
        dp[1] = all[1];
        dp[2] = Math.max(all[1],all[2]*2);
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+all[i]*i);
        }
        return dp[max];
    }
}